package com.lw.leetcode.other.c;

import java.util.Arrays;

/**
 * 927. 三等分
 */
public class ThreeEqualParts {

    public static void main(String[] args) {

        int[] arr = {1,0,1,0,1};
        ThreeEqualParts test = new ThreeEqualParts();

        int[] ints = test.threeEqualParts(arr);
        System.out.println(Arrays.toString(ints));
    }

    private int[] arr;

    public int[] threeEqualParts(int[] arr) {
        this.arr = arr;
        int length = arr.length;
        int oneCount = 0;
        for (int i : arr) {
            if (i == 1) {
                oneCount++;
            }
        }
        int[] values = new int[]{-1, -1};
        if (oneCount % 3 != 0) {
            return values;
        }
        if (oneCount == 0) {
            values[0] = 0;
            values[1] = length - 1;
            return values;
        }
        int itemCount = oneCount / 3;
        int tzero = getTzero();

        int fone = getFone(0, itemCount);
        int sone = getFone(fone + 1, itemCount);

        for (int i = 0; i < tzero; i++) {
            if (arr[fone + 1 + i] == 1 || arr[sone + 1 + i] == 1) {
                return values;
            }
        }

        int a = fone + tzero;
        int b = sone + tzero;
        int c = length - 1;
        int o = a;
        int t = b + 1;
        int ac = a + 1;
        int bc = b - a;
        int cc = c - b;
        int min = Math.min(ac, Math.min(bc, cc));
        while (min > 0) {
            if (arr[a] != arr[b] || arr[b] != arr[c]) {
                return values;
            }
            c--;
            b--;
            a--;
            min--;
            ac--;
            bc--;
            cc--;
        }
        values[0] = o;
        values[1] = t;
        return values;
    }

    private int getTzero() {
        int count = 0;
        for (int i = arr.length - 1; i > 0; i--) {
            if (arr[i] == 0) {
                count++;
            } else {
                return count;
            }
        }
        return count;
    }

    private int getFone(int st, int itemCount) {
        int length = arr.length;
        for (int i = st; i < length; i++) {
            if (arr[i] == 1) {
                itemCount--;
                if (itemCount == 0) {
                    return i;
                }
            }
        }
        return 0;
    }

}
